It has been quite a while since databases using computers became deeply involved with operations of organizations such as business enterprises and public institutions. One of the basic functions of the database is data searching by using a keyword. This function is to extract a document containing a specific keyword from a plurality of documents registered in the database. A tremendous number of documents are registered in the database, so that it is inefficient to analyze all the sentences contained within the documents to judge whether or not the keyword is contained therein every time there is a request from a user for searching.
Therefore, with most of the databases, it is possible to generate an index file for searching and to use it at the time of searching. The index file saves a list of corresponding documents as the search result for a specific keyword. The index file is updated regularly (e.g., every day at a prescribed time) in accordance with the actions of adding, deleting, and updating the document data. The use of the index file makes it possible to speed up the processing related to the searching.
In the meantime, in a database within an organization such as a business enterprise, a great number of pieces of information regarding the industrial secret and personal secret which are not allowed to be leaked to the outside of the organization are registered. Naturally, searching by using a keyword is required for such information as well. However, even when the document file itself is encrypted, there is a risk of leaking the information regarding which document contains which keyword from the saved index file. Thus, the simply encrypted index file cannot be used for search processing unless it is decrypted.
Non-Patent Documents 1 and 2 describe specific methods regarding the technique called Searchable Symmetric Encryption (referred to as SSE hereinafter) for improving the efficiency of performing keyword search while preventing information from being leaked from an index file. In Non-Patent Document 1, two SSE methods are depicted. Here, the method (referred to as SSE 1 hereinafter) depicted from page 15 to page 20 of that document will be described.
(Structure of SSE 1)
The SSE system (SSE1) depicted in Non-Patent Document 1 will be described. With this system, used is the data of a structure acquired by encrypting a linear list for searching a document with a keyword. For explanations, the preposition regarding the document and the keyword used therein will be described. A document group is expressed as D={D—1, - - - , D_n}, and each document D_j (j=1, - - - , n) has an identifier that can be used for discrimination. As the identifier, a file name, sequential numbers, or the like can be used.
FIG. 10 is an explanatory chart showing the structure of a keyword dictionary 810 (index file) Δ of the SSE system depicted in Non-Patent Document 1. The keyword dictionary 810 Δ is a set of document identifier information 810b containing w_i in D provided that the set of searchable keywords is Δ={w—1, - - - , w_d} and a search result is D(w_i) for a keyword 810a(w_i). Note that id(D, w_i, j) shows the identifier of the corresponding j-th document contained in D(w_i).
FIG. 10 shows a table of document identifier information 810b(id(D(w_i))) that is the search result based on a keyword 810a(w_i) contained in the dictionary Δ for the document group D. As one of the specific methods for saving such table as data, there is a method using a data structure called a linear list. As the linear list, there are a unidirectional list and a bidirectional list. Here, the linear list in a case of using the unidirectional list will be described.
FIG. 11 is an explanatory chart showing examples of unidirectional lists 820a to b in which three integer values are stored, which are used in the example of the SSE system depicted in Non-Patent Document 1 shown in FIG. 10. The two squares placed side by side show one element constituting a list. The one element is a node used herein. An integer value is written in the square on the left side. This is the data carried by the node. An arrow is written in the square on the right side, and the arrow indicates the next node on the list. This shows the address on the memory or the position on the storage device where each node is stored (simply referred to as address hereinafter).
Provided that the address and the value of the i-th node is ad_i and val_i, respectively, the i-th node can be expressed as (ad_i, val_i, ad_{i+1}) as a set of data of the address where the node is stored, the stored value, and the address where the next node is stored. Hereinafter, this expression is used. The end of the list can be expressed by using “Null” which is a special sign for the next address or for the value. In the unidirectional list 820a shown in FIG. 11 is an example of the former (the end of the list is shown by using an empty node), and the unidirectional list 820b is an example of the latter (the end of the list is shown by using “Null” value). For explanations, the head node in the linear list is referred to as the initial point, and the end of the node as the final point.
For recording the search result by using the linear list, used herein is a method which records the search result by using a search result array and an initial point array. In the search result array, a linear list of the search result for each keyword is recorded for each node. The linear lists for all the keywords are stored in the array. However, information regarding which address the initial point of the linear list is at for each keyword is not stored. The information regarding the initial point is stored in the initial point array that is the other array.
FIG. 12 is an explanatory chart showing a search result array 830 and an initial point array 840 in which the search result id_{i, 1}, id_{i, 2}, id_{i, 3} as the search result regarding a keyword w_i is put into a linear list in the case of the SSE system depicted in Non-Patent Document 1 shown in FIG. 10. As the initial point of the search result regarding the keyword w_i, ad_{i, 1} is recorded as the i-th element of the initial point array 840.
The corresponding relation such as “the initial point regarding w_i is recorded on the i-th” may be defined by using the information such as the order of the keyword within the dictionary in the alphabetical order. Any methods can be used as long as the corresponding relation can be defined uniquely. Here, the case where the initial point information for w_i is recorded on the i-th is used as an example for simplifying the explanation.
The method for acquiring the search result by using the linear list shown in FIG. 12 will be described. FIG. 12 shows the example of the case where the search result regarding the keyword w—1 is id_{i, 1}, id_{i, 2}, id_{i, 3}. Hereinafter, processing for reading out the search result regarding w_i from the arrays will be described.
1. First, the i-th address 840b=ad_{i, 1} of the initial point array 840 is read out.
2. Then, the first search result 830b=id_{i, 1} and the next address 830c=ad_{i, 2} that is the array where the next search result is stored are acquired by referring to the ad_{i, 1}-th element of the address 830a of the search result array 830.
3. Then, the second search result 830b=id_{i, 2} and the next address 830c=ad_{i, 3} that is the array where the next search result is stored are acquired by referring to the ad_{i, 2}-th element of the address 830a of the search result array 830.
4. Then, the third search result 830b=id_{i, 3} and the next address 830c=“Null value” that is the array where the next search result is stored are acquired by referring to the ad_{i, 3}-th element of the address 830a of the search result array 830. Thus, id_{i, 1}, id_{i, 2}, and id_{i, 3} are outputted as the search result regarding the keyword w_i.
With such method, when a document is added anew, information can be added as much as it is desired as long as there is an empty address in the array. Therefore, it is effective for the cases of using a database where documents are added one after another. In the meantime, it is evident that those arrays contain information regarding registered documents.
Acquired information is the information regarding what keyword a certain document contains and the similarity between two different documents. Thus, the use of auxiliary data constituted with the initial point array and the search result array in an encrypted database may result in leaking the information regarding the registered documents.
In order to make the keyword search efficient in the encrypted database while preventing information from being leaked, the SSE system used for supporting the search in the data in which the linear list is encrypted is proposed in Non-Patent Document 1 (SSE1).
In the explanations of this Description, a function where output is defined by input and key information (referred to as keyed hereinafter) and replacement where output is defined by input and key information (referred to as keyed replacement) are used. In a keyed function F, the output when the key is k and the input is x is expressed as F(k; x). The output when the input is n-pieces of numerical values such as x—1, - - - , x_n is written as F(k; x—1, - - - , x_n). The keyed replacement is expressed in the same manner. That is, the first element within a parenthesis is the key, and the second element on the right side of a semicolon is the input.
For encrypting the value, a common-key encryption system with which encryption processing and decryption processing are executed by using a common private key is used. An encryption function of the common key encryption is referred to as Enc( ) and a decryption function is referred to as Dec( ). The result acquired by encrypting data d with the key k is written as Enc(k; d), and the result acquired by decrypting a ciphertext c with the key k is written as Dec(k; c).
SSE1 is the system which uses the initial point array and the search result array described above as the auxiliary data used for searching in combination with the encryption processing. Hereinafter, the initial point array 840 and the search result array 830 on which encryption is applied are referred to as an encrypted initial point array 860 and an encrypted search result array 850, respectively. In the encrypted search result array, a list-type data structure (referred to as an encrypted linear list) acquired by modifying the linear list is used. This encrypted linear list will be described.
(Explanation of Encrypted Linear List)
The i-th node of the linear list is constituted with a set of three pieces such as (ad_i, val_i, ad_{i+1}). In the encrypted linear list, a common encryption key k_i is prepared for each node of the linear list, and data of four pieces such as (ad_i, Enc(k_i; val_i), Enc(k—1; k _{i+1}), Enc(k_i; ad_{i+1})) is defined as one set.
At the ad_i address, remaining three pieces of data are stored. By combining the values of the three pieces of stored data with k_i, it is possible to acquire val_i, k_{i+1}, and ad_{i+1} by decryption. This, the nodes after the i-th node can be acquired. Therefore, with the use of ad—1 and k—1, all the values stored in the encrypted linear list can be acquired. Hereinafter, those values are considered as the initial point information of the encrypted linear list.
For the end of the list, the next address may be set as a special sign “Null” as in the case of the linear list or a node where nothing is stored (referred to as an empty node hereinafter) may be set as a next address for expressing the end of the list. In this Description, hereinafter, used is a type of encrypted linear list in which an empty address is used for the next address stored at the end of the list. Hereinafter, a set of the next address stored in the last node and the key used for encrypting the next address is considered as the final point information.
The value, the encryption key of the next address, and the next address are all encrypted with a same key. However, those may be encrypted with different keys from each other by calculating different keys by using a keyed function having k_i as the key. In such case, K(k_i; 1), K(k_i; 2), K(k_i; 3) are calculated by using a keyed function K to use each of those as the encryption keys. 1, 2, and 3 merely are examples, and other values defined in advance may be used as well. Hereinafter, a case of using a single key will be described for making it easy to explain the concept.
(Explanation of Encrypted Search Result Array)
Subsequently, the encrypted search result array using the encrypted linear list will be described. FIG. 13 is an explanatory chart showing the encrypted initial point array 860 and the encrypted search result array 850 using the encrypted linear list in a case of the SSE system (SSE1) depicted in Non-Patent Document 1 shown in FIG. 10. The encrypted search result array 850 is an array in which the search results regarding a plurality of keywords are stored by using the encrypted linear lists. When the address of the initial point information of the encrypted linear list for each keyword w_i is written as ad_{w_i} and the key is written as k_{w_i}, the encrypted search result array 850 is a table which stores the encrypted search results, the encryption keys, and the next addresses 850b corresponding to the addresses 850a. 
The encrypted initial point array is an array in which the initial point information for each keyword is encrypted and stored. The corresponding keyword search result can be extracted from the encrypted search result array by using it. Nest, the encrypted initial point array will be described.
The encrypted initial point array is stored by processing ad_{w_i} and k_{w_i} which are a set of the encrypted linear list initial point information regarding each keyword w_i by using the encryption key k_e and the replacement key k_p. Provided that P is the keyed replacement and F is the keyed function, the encrypted initial point array is a table in which the encrypted address and the encryption key 860b, i.e., Enc(F(k_e; w_i); ad_{w_i}) and Enc(F(k_e; w_i); k_{w_i}), are stored at the address 860a=P(k_p; w_i). This processing using the encryption key k_e and the replacement key k_p is called the encryption processing of the initial point information.
That is, ad_{w_i} and k_{w_i} can be acquired by decrypting the ciphertext by using F{k_e; w_i} through referring to the P(k_p; w_i) address by using P(k_p; w_i) and F(k_e; w_i). As described earlier, the search result regarding w_i can be acquired from the encrypted search result array by using ad_{w_i} and k_{w_i}.
In the case where the initial point array and the search result array are used, the search result can be acquired without using any special information other than the keyword. In the meantime, in the case where the encrypted initial point array and the encrypted search result array are used, the encryption key k_e and the replacement key k_p are required for acquiring the initial point information. Thus, even when the encrypted initial point array and the encrypted search result array are stored, the search result regarding the keyword cannot be referred to without those keys. When P(k_p; w_i) and F(k_e; w_i) regarding a given keyword w_i are known, it is possible to refer to the corresponding search result.
Note that k_p and k_e may be generated as K(k; 1)=k_p and K(k; 2)=k_e by using a single key k and the keyed function K. “1” and “2” within each parenthesis merely are examples, and those may be other values given in advance. Hereinafter, in a case where it is assumed that k_p and k_e are used as a set, only one of the values such as the key k is to be written. With such method, the number of the keys to be stored and the storage capacity therefore can be reduced.
(Generation of Encrypted Initial Point Array and Encrypted Search Result Array)
The processing for generating the encrypted initial point array and the encrypted search result array can be classified into following four stages of processing.
1. Processing for generating search result.
2. Processing for generating commonly used data.
3. Processing for generating encrypted search result array.
4. Processing for generating encrypted initial point array.
“1. Processing for generating search result” is the processing for generating a keyword search result for an inputted document and the dictionary.
“2. Processing for generating commonly used data” is the processing for storing the initial point information of the encrypted linear list generated for each keyword in the encrypted search result array and storing the encrypted linear list generated for each keyword in the encrypted initial point array. In such processing, the initial point information of the encrypted linear list is used in common.“3. Processing for generating encrypted search result array” is the processing for generating the initial point information for each of the keywords. With this processing, an encrypted linear list is generated based on the search result generated for each keyword and the initial point information, and stored in the encrypted search result array. The keys for the address after the initial point are generated randomly in such a manner that no duplication occurs for the addresses. A method of using a counter or a method of storing empty addresses can be used. The use of the keyed replacement with the method of using the counter makes it difficult to know which addresses are linked as the list in the encrypted search result array.“4. Processing for generating encrypted initial point array” is the processing for encrypting the initial point information generated for each keyword by using the encryption key and storing it to the encrypted initial point array defined by the replacement key and the keyword.(Structure of Encrypted Database Device)
FIG. 14 is an explanatory chart showing the structure of an encrypted database device 900 which executes the SSE system (SSE1) depicted in Non-Patent Document 1 shown in FIG. 10. The encrypted database 900 is constituted with: a processor 901 which is the main body for executing a computer program; a storage module 902 which stores data; and an input/output module 903 which inputs/outputs data from the outside.
The processor 901 operates as an encrypted search result generating module 910, a trapdoor generating module 902 to be described later, and an encrypted database searching module 940 through operating an encrypted database program. Further, the storage module 902 operates as an encrypted search result storage module 920 which stores the encrypted initial point array and the encrypted search result array as the data regarding the search of the encrypted database.
FIG. 15 is an explanatory chart showing the structure of the encrypted search result generating module 910 shown in FIG. 14. The encrypted search result generating module 910 includes: a generation processing control unit 911; a search result generating unit 912; an initial point information generating unit 913; an encrypted linear list generating unit 914; and an initial point information encrypting unit 915. Further, the encrypted search result storage module 920 includes an encrypted search result array storage unit 921 and an encrypted initial point array storage unit 922.
The encrypted search result generating module 910 takes each of the keys, the documents to be registered, and the dictionary as input information from the outside via the input/output module 903, and stores the values to the encrypted search result array storage unit 921 and the encrypted initial point array storage unit 922, respectively, which are provided to the encrypted search result storage module 920.
The generation processing control unit 911 controls each of the functional units provided to the encrypted search result generating module 910 by taking the keys, the documents to be registered, and the dictionary as the input information. The search result generating unit 912 takes the documents and the dictionary as the input information, and outputs the search results of each of the keywords. The initial information generating unit 913 outputs the initial point information of the encrypted linear list to the outside via the input/output module 903.
The encrypted linear list generating unit 914 generates the encrypted linear list by taking the search result for each keyword and the initial point information as the input information, and stores it to the encrypted search result array storage unit 921. The initial point information encrypting unit 915 encrypts the initial point information of the encrypted linear list by using the inputted key, and updates the value to be stored to the encrypted initial information array storage unit 922 by using the key as the input information.
The encrypted search result array storage unit 921 stores the encrypted search result. The encrypted initial point array storage unit 922 stores the encrypted initial point array.
FIG. 16 is a flowchart showing an operation of the encrypted search result generating module 910 shown in FIG. 15. First, a key, a document group D={D—1, - - - , D_n}, and a dictionary Δ={w—1, - - - , w_d} are inputted to the generating processing control unit 911 via the input/output module 903 (step S951). The generation processing control unit 911 inputs the document group D and the dictionary Δ to the search result generating unit 912, and acquires the search result as the output thereof regarding the dictionary Δ of the document group D (step S952).
The generation processing control unit 911 executes following processing (step S953 to step S955) regarding the search result D(w_i) of each keyword w_i. First, the generation processing control unit 911 operates the initial point information generating unit 913 and acquires the initial point information X that is the output thereof (step S953). Subsequently, the generation processing control unit 911 inputs the initial point information X, the key, and w_i to the initial point information encrypting unit 915, and the initial information encrypting unit 915 encrypts the initial point information X by using the key and stores it to the address of the encrypted initial point array storage unit 922 defined by the key and the keyword (step S954).
In parallel to step S954, the generation processing control unit 911 inputs the initial point information X and D(w_i) to the encrypted linear list generating unit 914. The encrypted linear list generating unit 914 generates the encrypted linear list regarding the initial point information X and D(w_i), and stores it to the encrypted search result array storage unit 921 (step S955).
Next, the processing for searching data done with the encrypted initial point array and the encrypted search result array will be described. As descried above, the encrypted search result array is generated by using k_e and k_p.
As shown in FIG. 13, in order to extract the initial point information of the encrypted linear list regarding the keyword w_i from the encrypted initial array, P(k_p; w_i) and F(k_e; w_i) can be used. The set of P(k_p; w_i) and F(k_e; w_i) is referred to as a trapdoor for the keyword w_i. By using it, the search result regarding the keyword w_i can be extracted from the encrypted search result array.
FIG. 17 is an explanatory chart showing the structure of the trapdoor generating module 930 and the encrypted database searching module 940 shown in FIG. 14. The encrypted database searching module 940 includes an initial point information extracting unit 941 and a search result extracting unit 942.
The trapdoor generating module 930 calculates the trapdoor for w_i by taking the key k=(k_e, k_p) and the keyword w_i inputted from the outside via the input/output module 930 as the input. The initial point information extracting unit 941 decrypts a value η stored at address γ of the encrypted initial point array storage unit 922 by taking the trapdoor as the input, and outputs the initial point information of the encrypted linear list as the search result.
The search result extracting unit 942 takes the initial point information as the input, extracts the search result from the encrypted search result array storage unit 921 by using the inputted initial point information, and outputs it to the outside via the input/output module 903.
FIG. 18 is a flowchart showing an operation of the trapdoor generating module 930 shown in FIG. 14 and FIG. 17. When the key k=(k_e, k_p) and the keyword w_i are inputted to the trapdoor generating module 930 from the outside via the input/output module 930 (step S961), the trapdoor generating module 930 calculates γ=P(k_p; w_i) and η=F(k_e; w_i), and outputs the values of γ and η to the encrypted database searching module 940 (step S962).
FIG. 19 is a flowchart showing an operation of the encrypted database searching module 940 shown in FIG. 14 and FIG. 17. When γ and η of the trapdoor outputted in step S962 of FIG. 18 are inputted to the encrypted database searching module 940 (step S971), the initial point information extracting unit 941 upon receiving the input of γ and η outputs the initial point information to the search result extracting unit 942 (step S972). Then, the search result extracting unit 942 upon receiving the input outputs the search result to the outside via the input/output module 903 (step S973).
An example of the processing for registering the index for the document group D={D—1, - - - , D_n} and the dictionary Δ carried by the user into the database and an example of the operation of the search processing by using the index executed with SSE1 described above are as follows.
(Processing for Registering Search Data)
    1. A user generates key k.    2. Then, the user generates an encrypted search result by taking the key k, the document group D, and the dictionary Δ as the input.    3. Then, the user generates the key for encryption, and encrypts D by using the generated key.    4. Then, the encrypted search result and the ciphertext are transmitted to the encrypted database device 900 to be stored therein.(Processing for Searching)
The followings show the example of the operation of the search processing regarding the keyword w_i. The user herein is the user who holds the encryption key k legitimately and executes the processing for registering the data.    1. The user generates a trapdoor by taking k and w_i as the input, and transmits it to the encrypted database device 900.    2. The encrypted database device 900 executes the search processing by taking the trapdoor and the encrypted search result as the input to acquire the search result. The search result is an aggregation of the document identifiers.    3. The encrypted database device 900 transmits, to the user, the encrypted documents corresponding to the aggregation of the identifiers that are the result of the search processing.    4. The user decrypts the received documents, and acquires the search result.
The searching method by SSE1 described above has following characteristics.                First, a keyword itself is not used for requesting a search. Each trapdoor is converted from a keyword by a key held by the user. The key is selected randomly, and the corresponding relation between the trapdoor and the keyword is unknown to the encrypted database device 900 side.        Further, the search results for each of the keywords are rearranged and encrypted. Only the encrypted section regarding the corresponding keyword is decrypted by the trapdoor. Thus, those who do not have a legitimate key can only know that the entire search results correspond to some of the keywords w_i but cannot know which keyword it is.        
The information mentioned above is the information the database can acquire in a case of using the table and the linear list shown in FIG. 10. That is, the use of SSE1 makes it possible to prevent such information from being leaked.
Regarding this, there are following Patent Documents. Among those, Patent Document 1 describes a personal database generating method for recording user's preference and performing automatic recording accurately by using a video recording device. Patent Document 2 describes a database for searching a security policy for each terminal and each user. Patent Document 3 describes a database with which encrypted data can be searched at a high speed.    Patent Document 1: Japanese Unexamined Patent Publication 2002-300614    Patent Document 2: Japanese Unexamined Patent Publication 2008-053818    Patent Document 3: Japanese Unexamined Patent Publication 2008-517354    Non-Patent Document 1: Reza Curtmola, Juan A. Garay, Seny Kamara, RafailOstrovsky: Searchable symmetric encryption: improved definitions and efficientconstructions. ACM Conference on Computer and Communications Security 2006: 79-88    Non-Patent Document 2: Wakaha Ogata, Akira Kanaoka, Shin'ichiro Matsuo: What should be hidden in searchable symmetric encryption? SCIS2011
However, SSE1 has a risk of leaking the information regarding the registered document when adding, deleting, and updating a document. Hereinafter, this point will be described.
SSE1 does not have the function for adding, deleting, and updating a document. More specifically, it does not have the function for adding a specific document, the function for deleting a specific document, and the function for updating a specific document. As the processing regarding registration of a document, there is only the processing for generating encrypted search results anew for a plurality of documents. It is not practically possible to frequently repeat the processing for deleting all the encrypted search results and generating new encrypted search results with respect to a tremendous number and volume of documents.
New documents are to be added one after another to the database. Further, each of the registered documents is repeatedly updated and deleted one after another. Therefore, the functions for adding, deleting, and updating a document are essential. It is possible to achieve those functions by utilizing algorithm that constitutes SSE1. However, there is a risk of leaking the information. Hereinafter, the risks generated in each processing will be described.
(Risk when Adding Document)
A case of adding a document containing a keyword w_i whose document identifier is id_a is considered. At the end node of the encrypted linear list regarding the keyword w_i stored in the encrypted search result array, values acquired by encrypting the last identifier id of the search result, the key k_next and ad_next for encrypting the next address are stored.
Provided that the key for encrypting the address is k_end, the values Enc(k_end; id), Enc(k_end; k_next), and Enc(k_end; ad_next) are stored, respectively, in that node. Therefore, when the encrypted linear list having ad_next and k_next as the initial point information is added to the encrypted search result, the encrypted linear list in which the additional search result is stored after the current search result is stored to the encrypted search result array.
That is, an encrypted linear list of the added search result is generated by taking the final point information of the already-registered encrypted linear list as the initial point information, and the generated encrypted linear list is added to the encrypted search result array to execute the document adding processing. For executing the adding processing, the final point information regarding the aggregation W of all the keywords containing the document group to be added is simply required.
However, this data can be acquired by executing the search processing by using the trapdoor for each W and the encrypted search result array. Thus, when the trapdoor is transmitted to the user and the database after the registration processing mentioned above is performed, the database can acquire all the unencrypted search results regarding the keywords contained in W. That is, an extremely greater amount of information is to be leaked to the database compared to the case of requesting one operation of search processing to the database device.
(Risk when Deleting Document)
A case of deleting a document D_d whose document identifier is id_d is considered. It is to be noted that id_d is written somewhere on the encrypted linear lists of each of the keywords contained in the document. Through deleting those, the information regarding the target document can be eliminated from the index. Thus, it is necessary to know where on the encrypted linear list regarding each of the keywords id_d is written.
Such information can be acquired by executing the search processing by using the trapdoor for all the keywords contained in the document D_d. As in the case of the adding processing, when the same procedure is executed for the user and the database after performing the registration processing mentioned above, the database device acquires the unencrypted search results for all the keywords contained in D_d. In the case of deleting the document in such method, an extremely greater amount of information is to be leaked to the database also compared to the case of requesting one operation of search processing to the database device.
(Risk when Updating Document)
Update of a document can be executed by deleting the document that is before being updated and adding an updated document. Thus, the both risks described as the risks generated at the time of adding the document and at the time of deleting the document are to be generated.
The risks of leaking information generated at the time of adding, deleting, and updating the document with SSE1 described above, i.e., generated with the technique described in Non-Patent Document 1, are also generated with the other technique described in Non-Patent Document 1 and the technique described in Non-Patent Document 2. Further, the risks are not mentioned in Patent Documents 1 to 3. That is, currently, there is no known technique which can lighten or overcome those risks.
It is therefore an object of the present invention to provide an encrypted search database device, an encrypted search data adding/deleting method and an adding/deleting program, with which there is no risk of leaking information even when adding, deleting, and updating a document.